Some of the existing processors such as Central Processing Units (CPU) may perform the same type of operation on different data in parallel in response to one instruction called a Single Instruction Multiple Data (SIMD) instruction. Such processors that execute SIMD instructions are provided with registers called SIMD registers, which store different data to be processed in parallel, in combination. For example, assume that a SIMD instruction of s1+s2 is input to a processor when data A1 and A2 are stored in a SIMD register s1 and data B1 and B2 are stored in a SIMD register s2. In this case, the processor performs two addition operations, A1+B1 and A2+B2, in parallel in response to the single instruction.
One of methods for generating code including a SIMD instruction is to search a plurality of non-SIMD instructions for two or more instructions which specify the same operation type and are executable in parallel, and generate a SIMD instruction by combining the found instructions. For example, some of compliers that convert source code written in a high-level language into a machine-readable object code combine two or more instructions into a SIMD instruction while performing an optimization process. The number of instructions that are possible to be combined (parallelism) is different according to the architecture of a processor.
In this connection, there has been proposed a computer system which generates a trace dependency tree representing a dependency relationship among a plurality of instructions, searches the trace dependency tree for two or more instructions which belong to the same level and specify the same operation type, and merges the found instructions into a single SIMD instruction. Please see, for example, International Publication Pamphlet No. WO2006/007193.
When generating a SIMD instruction, instructions which do not have a dependency relationship and are executable in parallel are combined. As a method of searching for such a combination of instructions, there is a method of using a tree representing a dependency relationship among instructions, as described above. When a plurality of trees (or a plurality of partial trees belonging to one big tree) is generated by analyzing code, the generated trees are compared with each other, and a combination pattern is found by combining instructions which belong to different trees and specify the same operation type.
However, a plurality of trees generated by analyzing code may not have the same shape. Therefore, it may not be possible to find optimal combinations of instructions only by comparing instructions at the same level with each other as described above. Instructions at different levels may be possible to be combined. On the other hand, in order to find more combinations of instructions that are convertible to SIMD instructions, all combinations of instructions may be searched, irrespective of the tree structures. This searching, however, increases an amount of computation and causes efficiency loss.